В связи с невозможностью применения некоторых алгоритмов глобального логико-вероятностного вывода над цикличной вторичной структурой алгебраической байесовской сети (АБС) и относительно значительной временной сложностью алгоритма построения такой структуры, целесообразно предъявить критерий, который позволит. Проверять цикличность АБС до процесса построения вторичной структуры. Статья предлагает один из таких критериев, основывающийся на анализе вспомогательной структуры (полусиблингового графа) на предмет наличия циклов особого класса.
Условием работы алгоритмов глобального логико-вероятностного вывода в алгебраической байесовской сети (АБС) является отсутствие циклов в ее вторичной структуре. Первичная структура, над которой можно построить ациклическую вторичную, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в ее вторичной структуре без непосредственного построения вторичной структуры, а также оценка сложности этого алгоритма. В работе сформулирован алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в минимальном графе смежности полным перебором, доказана его корректность, оценена его сложность, предложено улучшение скорости работы этого алгоритма, доказана корректность и оценено время работы улучшенного алгоритма. Также рассмотрены возможности улучшения скорости работы этого алгоритма за счет использования алгоритмов построения элементов третичной полиструктуры АБС.
Алгебраическая байесовская сеть (АБС) — одна из логико-вероятностных графических моделей баз фрагментов знаний с неопределенностью. Алгоритмы глобального логико-вероятностного вывода АБС могут применяться при условии ацикличности еѐ вторичной структуры — графа смежности. Существующий метод преобразования графа смежности в дерево смежности ограниченно применим. Цель работы — предложить новые методы преобразования цикличной АБС к ацикличной, основывающиеся на структурной теореме о циклах минимальных графов смежности. В работе предложено два метода устранения циклов и доказана их корректность. Ключевые слова: алгебраические байесовские сети, четвертичная структура, вероятностные графические модели систем знаний, глобальная структура, ацикличность первичной структуры.
Алгебраические байесовские сети (АБС) относятся к классу логиковероятностных графических моделей систем знаний с неопределенностью, которые позволяются использовать интервальные оценки вероятности для представления неопределенности в знаниях. Одним из наиболее важных условий работы АБС является отсутствие циклов в их вторичной структуре. Первичная структура, над которой можно построить ациклическую АБС, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе анализа четвертичной структуры АБС, а также оценка сложности этого алгоритма. В работе сформулирован алгоритм выявления ацикличности, доказана его корректность, оценена его сложность и предложен ряд способов, направленных на ускорение работы этого алгоритма.
Третичная структура алгебраической байесовской сети (АБС) требуется для построения как случайного минимального графа смежности, так и всего множества минимальных графов смежности. Помимо этого она требуется для нахождения лучшей или оптимальной вторичной структуры для заданной первичной структуры АБС. Целью работы является формирование четко определенного понятия третичной структуры АБС и связанных с ней объектов на основе синтеза существующих подходов, а также исследование их свойств. Рассмотрены все существующие подходы к определению понятий«клика», «множество клик» и «граф клик», а также классификация клик максимального графа смежности. Построена единая терминологическая база для описания сопутствующих объектов, удовлетворяющая критериям неизбыточности и полноты систематизации. Третичная полиструктура определена как семейство графов, построенных над подмножествами множества сужений максимального графа смежности, ребра которых соответствуют тем или иным родственным отношениям, определенным в статье. Третичная структура определена как ориентированный граф, ребра которого проведены от родительских вершин к сыновьем, а вершинами являются сужения максимального графа смежности на веса ребер и вершин, а также на пустой вес (родительский граф над расширенным множеством значимых клик).
Роль третичной полиструктуры алгебраической байесовской сети (АБС) заметно возросла. Вводимая изначально в качестве вспомогательного объекта для построения вторичной структуры, третичная полиструктура нашла свое применение в анализе цикличности вторичной структуры без ее непосредственного построения и предполагается к использованию для глобального вывода в АБС. Цель работы — выделение (с последующей систематизацией и оценкой сложности) существующих алгоритмов построения элементов третичной полиструктуры из алгоритмов построения вторичной структуры. В работе рассмотрены существующие алгоритмы построения элементов третичной полиструктуры и оценено время их работы. Приводятся четыре алгоритма построения пустого графа над подмножествами значимых клик и два алгоритма построения родительского графа над множеством стереоклик.
Алгебраические байесовские сети (АБС) представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью. Работа алгоритмов логико-вероятностного вывода АБС зависит от выбора вторичной структуры, обычно представляемой графом смежности. В частности, возможности применения указанных алгоритмов препятствуют циклы, содержащиеся в этих графах. Цель работы — исследовать циклы вторичной структуры и выявить необходимые и достаточные условия цикличности или ацикличности минимальных графов смежности. Замкнутый сверху граф клик определяется как граф клик с добавленным к нему корнем (пракликой), полусиблинговые циклы определены как циклы, состоящие из вассалов, небратские полусиблинговые циклы определены как полусиблинговые циклы, пересечение всех вассалов, входящих в которые, пусто. Сформулирована и доказана теорема о циклах, утверждающая, что необходимым и достаточным условием цикличности минимального графа смежности является существование небратских полусиблинговых циклов в какой-либо клике. Следствием из теоремы является то, что все минимальные графы смежности, построенные над данной первичной структурой АБС, являются либо циклическими, либо ациклическими одновременно
Третичная структура алгебраической байесовской сети (АБС), представляемая в виде графа клик, важна для построения и анализа вторичной структуры АБС, а также для анализа ее первичной структуры. В статье предложены два алгоритма построения третичной структуры: алгоритм построения графа клик при помощи потомков и алгоритм построения графа клик снизу—вверх, доказана их корректность и оценено время работы. Оба алгоритма по заданному набору максимальных фрагментов знаний строят два упорядоченных множества, содержащие множества вершин и множества сыновей каждой клики. Приведены примеры первичных структур АБС, на которых первый алгоритм работает быстрее второго и, наоборот, второй — быстрее первого. Также установлены существование и единственность третичной структуры АБС для каждой первичной структуры АБС.
Предложен новый терминологический поход для формализации работы с графами смежности, основанный на понятии торакса, обозначающего множество ребер. Предложена новая система уточненных понятий теории графов смежности: вес, сужение, жила, магистральная связность, минимальный граф смежности. Уточнены также понятие графа смежности и формулировка теоремы о множестве минимальных графов смежности. Сформулирована и доказана лемма о независимом пути, утверждающая, что из набора непересекающихся множеств ребер найдутся два таких, что магистральный путь между ними не пересекается ни с каким множеством из набора.
Алгебраические байесовские сети (АБС), представляющие собой логико-вероятностную графическую модель систем знаний с неопределенностью и позволяют работать в том числе с интервальными оценками вероятности. Работа алгоритмов АБС во многом опирается на вторичную структуру, представляемую графов смежности. Особую роль играет множество минимальных графов смежности, которое содержат наиболее «эффективные» вторичные структуры. Цель данной статьи — оценить мощность указанного множества. Введено понятие объема, характеризующее число вершин, входящих в компоненты связности строго сужения. Использование понятия объема позволила выразить коэффициент раздробленности клик — ее численную характеристику, через которую была выражена мощность множества минимальных графов смежности.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи самоуправляемых клик), а также два улучшения, каждое из которых реализуется в отдельном алгоритме; однако нет алгоритма, который бы реализовал оба улучшения. Цельюданной работы является создание такого алгоритма, который бы реализовывал одновременно ряд улучшений базового алгоритма, вследствие чего он был бы более эффективным, чем существующие.Такой алгоритм был предложен, его корректность доказана.
Существует эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов (при помощи само-управляемых клик), однако он может быть улучшен путем привлечения результатов активно разрабатывающейся теории глобальной структуры алгебраической байесовской сети. Целью данной работы является разработать улучшенную версию этого алгоритма за счет усовершенствованного построения множества вершин, входящих в клики: вместо полного перебора всех весов клик и вершин производить поиск для каждой клики ее потомков среди других клик. Предложенное улучшение легко в основу нового алгоритма построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников, корректность которого также была доказана.
Известен эффективный алгоритм построения множества минимальных графов смежности по заданному набору максимальных фрагментов знаний (при помощи самоуправляемых клик), однако этот алгоритм может быть улучшен путем привлечения разработанной теории глобальной структуры алгебраической байесовской сети. Цель работы — улучшить работу этого алгоритма за счет усовершенствованного построения владений (компонент связности строгих сужений) — ключевых объектов в построении данного множество: строить их не прямым поиском, а путем анализа пересечений множеств вершин детей соответствующих клик. Был предложен алгоритм, реализующий предложенные улучшения, и доказана его корректность.
Алгебраические байесовские сети представляют собой логико-вероятностную графическую модель систем знаний с неопределенностью и могут быть применимы в обработкестатистических данных и машинном обучении. Важную роль в их работе играет вторичная структура, представляемая в виде графа смежности. Данная статья вводит классификацию клик минимальных графов смежности в зависимости от числа их детей, а также числа вхождения в них числа особых ребер. Получено восемь различных типов клик, для которых были получены и обоснованыоценки числа зависимых от них компонент (феодов и жил).
1 - 14 из 14 результатов